package com.fjl.array.leetcode713;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/3/21 10:40
 */
/*
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：
    输入：nums = [10,5,2,6], k = 100
    输出：8
    解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
    需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
示例 2：
    输入：nums = [1,2,3], k = 0
    输出：0
 */
public class Clazz {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        int window = 1;
        int left = 0, right = 0;
        while (right < n) {
            // 扩大窗口，并更新窗口数据
            window *= nums[right];
            right++;
            while (window >= k && left < right) {
                // 缩小窗口，并更新窗口数据
                window /= nums[left];
                left++;
            }
            // 现在必然是一个合法的窗口，但注意思考这个窗口中的子数组个数怎么计算：
            // 比方说 left = 1, right = 4 划定了 [1, 2, 3] 这个窗口（right 是开区间）
            // 但不止 [left..right] 是合法的子数组，[left+1..right], [left+2..right] 等都是合法子数组
            // 所以我们需要把 [3], [2,3], [1,2,3] 这 right - left 个子数组都加上
            res += right - left;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Clazz().numSubarrayProductLessThanK(new int[]{10,5,2,6}, 100));
    }
}
